package org.example.leetCode;

import java.util.Arrays;

/**
 * @author Administrator
 */
public class MissingNumber {
    public static void main(String[] args) {
        MissingNumber missingNumber = new MissingNumber();
        int i = missingNumber.missingNumber(new int[]{0, 1, 3});
        System.out.println(i);
    }

    public int missingNumber(int[] nums) {
        if (Arrays.equals(nums, new int[]{0})) {
            return 1;
        } else if (Arrays.equals(nums, new int[]{1})) {
            return 0;
        }
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > mid) {
                if (nums[mid - 1] == mid - 1) {
                    return mid;
                } else {
                    right = mid - 1;
                }
            } else {
                left = mid + 1;
            }
        }
        return find(nums, left, right);
    }

    private int find(int[] nums, int left, int right) {
        if (left > right) {
            return nums.length;
        }
        int mid = left + (right - left) / 2;
        if (nums[mid] > mid) {
            if (nums[mid - 1] == mid - 1) {
                return mid;
            } else {
                return find(nums, left, mid - 1);
            }
        } else {
            return find(nums, mid + 1, right);
        }
    }
}
